Forward error correction FEC is a powerful tool to increase power and spectrum efficiency, especially in wireless communications. Turbo product codes TPCs are a class of FEC codes that define a relatively large code from smaller block codes. FIG. 1 is a simplified example of a full TPC block, where I indicates an information bit (payload) and P indicates a parity bit (error correction). Each of the rows or columns may be considered a (8,4) Hamming Code, where the parenthetical indicates (codeword length, information bits per codeword). This code takes 4 information bits, computes 3 parity bits of Hamming Code, and one additional parity bit of all the 4 information bits and the 3 Hamming code parity bits to create an 8-bit code word. That one additional parity bit in the codeword is termed an extended parity bit, because as will be seen it is computed differently than other parity bits. Each bit in the final row and column of FIG. 1 is an extended parity bit. In systematic form a code word has the form: I1I2I3I4P1P2P3P4. Here the symbol Ij denotes information bit, and P1 through P3 denote parity bits generated by the Hamming Code, and P4 denotes an extended parity bit for all 7 bits (the entire codeword except for the an extended parity bit).
A traditional TPC encoder starts with the first row of information bits, calculates and appends the parity bits, denoted PH (horizontal parity), and then moves to the second row. This is repeated for each row. Next, that TPC encoder starts with the first column of information bits, calculates and appends the parity bits for the column, denoted by PV (vertical parity), and moves to the next column. Those bits designated PVH are termed parity on parity bits, because they represent parity of only other parity bits, and are not generated directly from any information bit(s). It is important to note three items: a) the parity on parity bits PVH can be generated as row parities or column parities and in both cases the result is the same parity bit patterns, i.e. PVH=PHV; b) different code lengths may be used for the horizontal and vertical blocks; and c) the illustrated two-dimensional TPC code may be expanded to three dimensions. For this two dimensional code, the encoder operates on both rows and columns, so the encoding process is (8,4)2 to generate a rate ¼ code. Typical TPC codes employ a higher coding rate, as will be seen in the example used hereafter.
The architecture of a traditional TPC encoder 20 is shown in FIG. 2, and the related timing diagram is shown in FIG. 3. These figures are described in the context of a two dimensional code that has a (128,120) extended single error correcting BCH code or equivalently an extended Hamming code as both its row and column codes. A BCH (Bose, Ray-Chaudhuri, Hocquenghem) code is a multi-level, cyclic error-correcting code used to correct random error. A Hamming code is a special case of a (single-error correcting) BCH code and is used herein as a non-limiting example.
As will be seen, the extended parity bits are computed separately in the encoder. Considering a codeword with 120 information bits and the 7 normally-computed parity bits, the generator function of the single error correcting (127,120)BCH code with Hamming distance of 4 is g(x)=X7+X3+1, or (010001001), or (211)8. This generator function is implemented with a 7-bit length linear feedback shift register LFSR 22 for the first seven parity bits (P6→P0) as shown in FIG. 2, using a one-bit accumulator 24 for each parity bit and an adder 25 interspersed to tap different information bits at different clock cycles to assure each resulting parity bit P0-P6 in the codeword represents a different combination. This LFSR 22 is reset at the beginning of an arriving new codeword. Each codeword has 120 information bits fed into the encoder 20 along a Data_in line 26. The encoder is a systematic encoder and hence the first 120 bits of the codeword output on the Data_out line 28 equals the first 120 information bits arriving along the Data_in line 26. The first information bit A0 is also input to the LFSR 22 at the adder 25. Each of the next information bits A1, A2, A3, . . . A119 from the Data_in line 26 move incrementally through the seven-bit length LFSR 22 At that time, signal line S1 30 switches a first multiplexer 32 to receive inputs from the LFSR 22 rather than the Data_in line 26, and the seven parity bits P6-P0 from the LFSR 22 append to the end of the 120 information bits A119-A0. Throughout, each and every bit is fed into an extended parity register 34 of bit-length one. Once the final LFSR 22 parity bit P0 is output from the first multiplexer 30, a signal S0 36 changes the input of a second multiplexer 38 from the first multiplexer 32 to the extended parity register 34, and the final parity bit PP is appended to follow the seven LFSR 22 parity bits P6-P0, thus completing the row-codeword output on the Data_out line 28.
The columns are encoded with the same hardware, but with one information or parity bit from each row input into the encoder 20 to generate the parity bits for that column. The row-outputs of the FIG. 2 encoder 20 may be stored in a RAM and then re-input as column information bits along the Data_in line 26. The information bits after the column encoding are the same ones output from the row encoding and stored in memory, so they may be handled in two ways: they may be output and overwrite those corresponding information bits stored in the RAM from the various row encoding processes, or they may be deleted without being output from the column encoding process so that only the column parity bits are output from the column encoding process to the RAM. As noted above, the PVH bits may be computed as columns or rows. As with the information bits in column encoding, the PV or PH bits from the RAM that are used to generate the PVH bits may be deleted before being output from the PVH generation process, or may be re-entered into the RAM to overwrite their corresponding PV or PH values already in RAM from the previous row or column encoding process.
FIG. 3 shows the timing diagram for encoding one row by the encoder 20 of FIG. 2 in view of the clock pulses 40, with one-bit processing. The New_Row signal 42 resets the accumulators 24 for all eight parity bits P6-P0 and PP to initiate a new row codeword. Each information bit A119-A0 input on the Data_in line 26 moves one position on each clock pulse until all information bits of the block are input. At that point, signal S1 30 goes high, suspending entry of the next row of information bits of the block while the parity bits P6-P0 are output from the LFSR 22. Signal S0 36 then goes high to output the extended parity bit PP. The individual output bits for a single row are seen at the Data-out line 28, one bit per clock cycle. Each row is generated in that manner, and thereafter the column parity bits are generated using the same encoder hardware 20 by either of the methods noted above.
This invention improves upon the described prior art architecture in hardware and speed, as will be detailed below.